COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	@* \[20] Edge structures.
C00068 ENDMK
C⊗;
@* \[20] Edge structures.
Now we come to \MF's internal scheme for representing what the user can
actually ``see,'' the edges between pixels. Each pixel has an integer
weight, obtained by summing the weights on all edges to its left. \MF\
represents only the nonzero edge weights, since most of the edges are
weightless; in this way, the data storage requirements grow only linearly
with respect to the number of pixels per point, even though two-dimensional
data is being represented. (Well, the actual dependence on the underlying
resolution is order $n\log n$, but the the $\log n$ factor is buried in our
implicit restriction on the maximum raster size.) The sum of all edge
weights in each row should be zero.

The data structure for edge weights must be compact and flexible,
yet it should support efficient updating and display operations. We
want to be able to have many different edge structures in memory at
once, and we want the computer to be able to translate them, reflect them,
or merge them together with relative ease.

\MF's solution to this problem requires one single-word node per
nonzero edge weight, plus one two-word node for each row in a contiguous
set of rows. There's also a header node that provides global information
about the entire structure.

@ Let's consider the edge-weight nodes first. The |info| field of such
nodes contains both an $m$~value and a weight~$w$, in the form
$8m+w+c$, where $c$ is a constant that depends on data found in the header.
We shall consider $c$ in detail later; for now, it's best just to think
of it as a way to compensate for the fact that $m$ and~$w$ can be negative,
together with the fact that an |info| field must have a value between
|min_halfword| and |max_halfword|. The $m$ value is an unscaled $x$-coordinate,
so it satisfies $\vert m\vert<
4096$; the $w$ value is always in the range $1\L\vert w\vert\L3$. We can
unpack the data in the |info| field by fetching |ho(info(p))=
info(p)-min_halfword| and dividing this nonnegative number by~8;
the constant~$c$ will be chosen so that the remainder of this division
is $4+w$. Thus, for example, a remainder of~3 will correspond to
the edge weight $w=-1$.

Every row of an edge structure contains two lists of such edge-weight
nodes, called the |sorted| and |unsorted| lists, linked together by their
|link| fields in the normal way. The difference between them is that we
always have |info(p)≤info(link(p))| in the |sorted| list, but there's no
such restriction on the elements of the |unsortgww←"qαS#*βK↔π≡{9β≠␈⊂4+SFKMβ∪O≠S';∨#'?9εKMβSFQβ'"β←?Wf!βSπ↑)βW;v+∂↔O≡K'3Jβ3?;:βS=βn';S∞K84+.#∨∃7>+'∨#"β3'O'→β'9π≠?KS.!β?K&+Iβ←FK3∃β&C↔e∨⊗)β↔Ns≥βWε#πS↔#YβW"β←#↔rβ←∀4Vs↔↔⊃π#=βC⊗{∂↔O~βπ9β.sS'K*βK?]ε3K?5εc↔≠Qπ#=βKN;#QβNqβ?K&+Iβ?2βS#∀hQ∪5⊂W3π3W/→1β'";Mβ≠∞KK3eε+πOeε;⊃β∂+'∂-π#=βO␈∪Qβ¬π≠#?K"β3'O"β?→β.sO?K&+⊂4+.c↔7↔w#Mβπv!βS=εk↔K∨*βS#↔jβ';SzβC3π≡)βπ7}s≥βSF+'Iβ≡{KS↔"β∂?#␈∪SM8hR≠WK&C↔K7␈∪∃1β&C∃β≠∞≠QβSFQβSF)βsWw≠?KS.#qβ3O≠Qβ'~β↔7C'Iβ∂πrβO?7/#'7↔~β∀4W+O↔⊃π#=β∨}{⊃βπ'3π;S∞;∃1β⊗+∂πW≡)β'Qε33??→βWMπ#=β∂}s∂3W&)βS#∂!β¬βεKS'∨+3πHhSK?]εCπMβv{Qβ∂F;∨↔"βO';≡)βS#*β3πO"βS'7*β←∃β≡{KS↔"β'Q8hP4*SF)β≠'v1βsfK;/qε{→βSF)βsO␈∪S↔∪bβ3'O"β←'3bβ∃βg≠↔;SNs↔3qbβ←#'≡AβC?NsSMβ&x4+¬π≠C↔∂N1β?v)7←?⊗!β;?&)β←#␈≠∃βsNs≠?qε3'↔3"β'Mβ/≠O↔;&Kπ33Jβ';≠Ns'S∃ZβS#'_h+≠π≡K3'S∂#↔Mβ&C∃βO␈∪S';:βπ;⊃εk↔K∨Ns≥β?ε+KπSN{;M9¬##∃β6K;π1πc3';←aβ?→π##∀4WcW;O␈∪S↔∪bβ3'O"β←'3bβ∃β.KS#↔∩βs;Wfcqβ?∩βs[?N#q1β>C↔K∃πc[?'#k;W3bYGp4VKMβW≡+⊃βSzβπ[?N#';≥π∪↔∪'∨β3πgNs≥β∪∂#¬βSFQβ#∂→β;?"β∂#πv;↔⊃hhR¬βs6{'∪qπ3π3W*β'Mβ∨#?K↔"βπQβ&C∃β#.⊃β?2βS#∀hSW;O␈∪S↔⊃εc'OQπ;#↔;/3↔Iβ&C∃β∂␈∪K↔Oε{;∪'v9βK?:β#πMε∪↔↔9ε#'OCfg↔⊃ph(4*ε!βk↔⊗xc]u h*β⊃π3?'⊃kk;W3bYD4(hR↓r'vKS'πfKk∃β&3∃ε+;SKN+M99t↓yt4VK;≠=G≠↔;SNs↔1&}kπ`cF3≠←␈∪⊃mβ←c3';ZCO↔;&K;↔1Kk;W3gcx4(hR↓αSF)βK??→βS#.kO↔36+Mβπ⊗)βK↔π∪↔O↔w#↔⊃β↔IβK?:k#↔π&+Iβ;}#↔Mβ&CπP4V≠?;S∞K9β≠␈+Iβ3Ns-β≠N+3∪MrαS←=ε{→βSF+O∃β6{WI1πcO?K&+∪qβ∞s⊃βs.sO?K&+∪q0hSC?'w!βS=π##∃β6KKOQεKS↔7~β?→β&C∃β↔&;∃7←.K∨#Qεc'OS~β+WO"β7↔;&K?;↔"p4*SF)β?SF+IβS>y1βsfK;/qε;⊃βf[;'3baβC?NsQβSzβS#∃εC↔π∪/∪Mβ?2βS#∃π#←<4V∪+π≡+;Qβ⊗{←M9∧K→βsπaβC?NsSMβ&yβS#*β#↔π&+Iβ≠␈⊃βK?:β;W7⊗+Hkswa1βSF+84+fc';-G↓'qβε{';S~βWAβ&yβS#*β#↔π&+Iβ≠␈⊃βK?9Ss9-∂a1βπv!βs/vK1#AOaβC?NsSL4V#?←9π#=βSF+%⊃Z header for row~|n-1|. This double linking makes it
convenient to move through consecutive rows either upward or downward;
as usual, we have |link(knil(p))=knil(link(p))=p| for all row headers~|p|.

The row associated with a given value of |n| contains weights for
edges that run between the lattice points |(m,n)| and |(m,n+1)|.

@d knil==info {inverse of the |link| field, in a doubly linked list}
@d sorted_loc(#)==#+1 {where the |sorted| link field resides}
@d sorted(#)==link(sorted_loc(#)) {beginning of the list of sorted edge weights}
@d unsorted(#)==info(#+1) {beginning of the list of unsorted edge weights}
@d row_node_size=2 {number of words in a row header node}

@ The main header node |h| for an edge structure has |link| and |knil|
fields that link it above the topmost row and below the bottommost row.
It also has fields called |m_min|, |m_max|, |n_min|, and |n_max| that
bound the current extent of the edge data: All |m| values in edge-weight
nodes should lie between |m_min(h)-4096| and |m_max(h)-4096|, inclusive.
Furthermore the topmost row header, pointed to by |knil(h)|,
is for row number |n_max(h)-4096|; the bottommost row header, pointed to by
|link(h)|, is for row number |n_min(h)-4096|.

The offset constant |c| that's used in all of the edge-weight data is
represented implicitly in |m_offset(h)|; its actual value is
$$\hbox{|c=min_halfword+zero_w+8*m_offset(h)|.}$$
Notice that it's possible to shift an entire edge structure by an
amount $(\Delta m,\Delta n)$ by adding $\Delta n$ to |n_min(h)| and |n_max(h)|,
adding $\Delta m$ to |m_min(h)| and |m_max(h)|, and subtracting
$\Delta m$ from |m_offset(h)|;
none of the other edge data needs to be modified. Initially the |m_offset|
field is~4096, but it will change if the user requests such a shift.
The contents of these five fields should always be positive and less than
8192; |n_max| should, in fact, be less than 8191.  Furthermore
|m_min+m_offset-4096| and |m_max+m_offset-4096| must also lie strictly
between 0 and 8192, so that the |info| fields of edge-weight nodes will
fit in a halfword.

The header node of an edge structure also contains two somewhat unusual
fields called |last_window(h)| and |last_window_time(h)|. When this
structure is displayed in window~|k| of the user's screen, after that
window has been updated |t| times, \MF\ sets |last_window(h)←k| and
|last_window_time(h)←t|; it also sets |unsorted(p)←void| for all row
headers~|p|, after merging any existing unsorted weights with the sorted
ones.  A subsequent display in the same window will be able to avoid
redisplaying rows whose |unsorted| list is still |void|, if the window
hasn't been used for something else in the meantime.

A pointer to the row header of row |n_pos(h)-4096| is provided in
|n_rover(h)|. Most of the algorithms that update an edge structure
are able to get by without random row references; they usually
access rows that are neighbors of each other or of the current |n_pos| row.
Exception: If |link(h)=h| (so that the edge structure contains
no rows), we have |n_rover(h)=h|, and |n_pos(h)| is irrelevant.

@d zero_field=4096 {amount added to coordinates to make them positive}
@d n_min(#)==info(#+1) {minimum row number present, plus |zero_field|}
@d n_max(#)==link(#+1) {maximum row number present, plus |zero_field|}
@d m_min(#)==info(#+2) {minimum column number present, plus |zero_field|}
@d m_max(#)==link(#+2) {maximum column number present, plus |zero_field|}
@d m_offset(#)==info(#+3) {translation of $m$ data in edge-weight nodes}
@d last_window(#)==link(#+3) {the last display went into this window}
@d last_window_time(#)==mem[#+4].int {after this many window updates}
@d n_pos(#)==info(#+5) {the row currently in |n_rover|, plus |zero_field|}
@d n_rover(#)==link(#+5) {a row recently referenced}
@d edge_header_size=6 {number of words in an edge-structure header}
@d valid_range(#)==(abs(#-4096)<4096) {is |#| strictly between 0 and 8192?}

@<Declare the null value routines@>=
procedure init_edges(@!h:pointer); {initialize an edge header to null values}
begin knil(h)←h; link(h)←h;@/
n_min(h)←zero_field+4095; n_max(h)←zero_field-4095;
m_min(h)←zero_field+4095; m_max(h)←zero_field-4095;
m_offset(h)←zero_field;@/
last_window(h)←0; last_window_time(h)←0;@/
n_rover(h)←h; n_pos(h)←0;@/
end;
@#
function new_edges:pointer; {creates a new (empty) edge structure}
var @!h:pointer; {the new header node}
begin h←get_node(edge_header_size); init_edges(h);
new_edges←h;
end;

@ When a lot of work is being done on a particular edge structure, we plant
a pointer to its main header in the global variable |cur_edges|.
This saves us from having to pass this pointer as a parameter over and
over again between subroutines.

Similarly, |cur_wt| is a global weight that is being used by several
procedures at once.

@<Glob...@>=
@!cur_edges:pointer; {the edge structure of current interest}
@!cur_wt:integer; {the edge weight of current interest}

@ The |fix_offset| routine goes through all the edge-weight nodes of
|cur_edges| and adds a constant to their |info| fields, so that
|m_offset(cur_edges)| can be brought back to |zero_field|. (This
is necessary only in unusual cases when the offset has gotten too
large or too small.)

@p procedure fix_offset;
var @!p,@!q:pointer; {list traversers}
@!delta:integer; {the amount of change}
begin delta←8*(m_offset(cur_edges)-zero_field);
m_offset(cur_edges)←zero_field;
q←link(cur_edges);
while q≠cur_edges do
	begin p←sorted(q);
	while p>sentinel do
		begin info(p)←info(p)-delta; p←link(p);
		end;
	p←unsorted(q);
	while p>void do
		begin info(p)←info(p)-delta; p←link(p);
		end;
	q←link(q);
	end;
end;

@ The |edge_prep| routine makes the |cur_edges| structure ready to
accept new data whose coordinates satisfy |ml≤m≤mr| and |nl≤n≤nr-1|,
assuming that |-4096<ml≤mr<4096| and |-4096<nl≤nr<4096|. It makes
appropriate adjustments to |m_min|, |m_max|, |n_min|, and |n_max|,
adding new empty rows if necessary.

@p procedure edge_prep(@!ml,@!mr,@!nl,@!nr:integer);
var @!delta:halfword; {amount of change}
@!p,@!q:pointer; {for list manipulation}
begin ml←ml+zero_field; mr←mr+zero_field;
nl←nl+zero_field; nr←nr-1+zero_field;@/
if ml<m_min(cur_edges) then m_min(cur_edges)←ml;
if mr>m_max(cur_edges) then m_max(cur_edges)←mr;
if ¬ valid_range(m_min(cur_edges)+m_offset(cur_edges)-zero_field) ∨@|
 ¬ valid_range(m_max(cur_edges)+m_offset(cur_edges)-zero_field) then
	fix_offset;
if link(cur_edges)=cur_edges then {there are no rows}
	begin n_min(cur_edges)←nr+1; n_max(cur_edges)←nr;
	end;
if nl<n_min(cur_edges) then
	@<Insert exactly |n_min(cur_edges)-nl| empty rows at the bottom@>;
if nr>n_max(cur_edges) then
	@<Insert exactly |nr-n_max(cur_edges)| empty rows at the top@>;
end;

@ @<Insert exactly |n_min(cur_edges)-nl| empty rows at the bottom@>=
begin delta←n_min(cur_edges)-nl; n_min(cur_edges)←nl;
p←link(cur_edges);
repeat q←get_node(row_node_size); sorted(q)←sentinel; unsorted(q)←void;
knil(p)←q; link(q)←p; p←q; decr(delta);
until delta=0;
knil(p)←cur_edges; link(cur_edges)←p;
if n_rover(cur_edges)=cur_edges then n_pos(cur_edges)←nl-1;
end

@ @<Insert exactly |nr-n_max(cur_edges)| empty rows at the top@>=
begin delta←nr-n_max(cur_edges); n_max(cur_edges)←nr;
p←knil(cur_edges);
repeat q←get_node(row_node_size); sorted(q)←sentinel; unsorted(q)←void;
link(p)←q; knil(q)←p; p←q; decr(delta);
until delta=0;
link(p)←cur_edges; knil(cur_edges)←p;
if n_rover(cur_edges)=cur_edges then n_pos(cur_edges)←nr+1;
end

@ The |print_edges| subroutine gives a symbolic rendition of an edge
structure, for use in `\&{show}' commands. A rather terse output
format has been chosen since edge structures can grow quite large.

@<Declare subroutines for printing expressions@>=
@t\4@>@<Declare the procedure called |print_weight|@>@;@/
procedure print_edges(@!s:str_number);
var @!p,@!q:pointer; {for list traversal}
@!n:integer; {row number}
begin print_diagnostic("Edge structure",s);
p←knil(cur_edges); n←n_max(cur_edges)-zero_field;
while p≠cur_edges do
	begin print_nl("row "); print_int(n); print_char(":");
	q←unsorted(p);
	while q>void do
		begin print_weight(q); q←link(q);
		end;
	print(" |"); q←sorted(p);
	while q>sentinel do
		begin print_weight(q); q←link(q);
		end;
	p←knil(p); decr(n);
	end;
end_diagnostic(true);
end;

@ @<Declare the procedure called |print_weight|@>=
procedure print_weight(@!q:pointer);
var @!w,@!m:integer; {unpacked weight and coordinate}
@!d:integer; {temporary data register}
begin d←ho(info(q)); w←d mod 8; m←(d div 8)-m_offset(cur_edges);
if file_offset>max_print_line-9 then print_nl(" ")
else print_char(" ");
print_int(m);
while w>zero_w do
	begin print_char("+"); decr(w);
	end;
while w<zero_w do
	begin print_char("-"); incr(w);
	end;
end;

@ Here's a trivial subroutine that copies an edge structure. (Let's hope
that the given structure isn't too gigantic.)

@p function copy_edges(@!h:pointer):pointer;
var @!p,@!r:pointer; {variables that traverse the given structure}
@!hh,@!pp,@!qq,@!rr,@!ss:pointer; {variables that traverse the new structure}
begin hh←get_node(edge_header_size);
mem[hh+1]←mem[h+1]; mem[hh+2]←mem[h+2];
mem[hh+3]←mem[h+3]; mem[hh+4]←mem[h+4]; {we've now copied |n_min|, |n_max|,
	|m_min|, |m_max|, |m_offset|, |last_window|, and |last_window_time|}
n_pos(hh)←n_max(hh)+1;n_rover(hh)←hh;@/
p←link(h); qq←hh;
while p≠h do
	begin pp←get_node(row_node_size); link(qq)←pp; knil(pp)←qq;
	@<Copy both |sorted| and |unsorted| lists of |p| to |pp|@>;
	p←link(p); qq←pp;
	end;
link(qq)←hh; knil(hh)←qq;
copy_edges←hh;
end;

@ @<Copy both |sorted| and |unsorted|...@>=
r←sorted(p); rr←sorted_loc(pp); {|link(rr)=sorted(pp)|}
while r>sentinel do
	begin ss←get_avail; link(rr)←ss; rr←ss; info(rr)←info(r);@/
	r←link(r);
	end;
link(rr)←sentinel;@/
r←unsorted(p); rr←temp_head;
while r>void do
	begin ss←get_avail; link(rr)←ss; rr←ss; info(rr)←info(r);@/
	r←link(r);
	end;
link(rr)←r; unsorted(pp)←link(temp_head)

@ Another trivial routine flips |cur_edges| about the |x|-axis
(i.e., negates all the |y| coordinates), assuming that at least
one row is present.

@p procedure y_reflect_edges;
var @!p,@!q,@!r:pointer; {list manipulation registers}
begin p←n_min(cur_edges);
n_min(cur_edges)←zero_field+zero_field-1-n_max(cur_edges);
n_max(cur_edges)←zero_field+zero_field-1-p;
n_pos(cur_edges)←zero_field+zero_field-1-n_pos(cur_edges);@/
p←link(cur_edges); q←cur_edges; {we assume that |p≠q|}
repeat r←link(p); link(p)←q; knil(q)←p; q←p; p←r;
until q=cur_edges;
last_window_time(cur_edges)←0;
end;

@ It's somewhat more difficult, yet not too hard, to reflect about the |y|-axis.

@p procedure x_reflect_edges;
var @!p,@!q,@!r,@!s:pointer; {list manipulation registers}
@!m:integer; {|info| fields will be reflected with respect to this number}
begin p←m_min(cur_edges);
m_min(cur_edges)←zero_field+zero_field-m_max(cur_edges);
m_max(cur_edges)←zero_field+zero_field-p;
if ¬ valid_range(m_min(cur_edges)+m_offset(cur_edges)-zero_field)∨@|
 ¬ valid_range(m_max(cur_edges)+m_offset(cur_edges)-zero_field) then
	fix_offset;
m←(m_offset(cur_edges)*8+zero_w+min_halfword)*2;
p←link(cur_edges);
repeat @<Reflect the edge-and-weight data in |sorted(p)|@>;
@<Reflect the edge-and-weight data in |unsorted(p)|@>;
p←link(p);
until p=cur_edges;
last_window_time(cur_edges)←0;
end;

@ We want to change the sign of the weight as we change the sign of the
|x|-coordinate. Fortunately, it's easier to do this than to negate
one without the other.

@<Reflect the edge-and-weight data in |unsorted(p)|@>=
q←unsorted(p);
while q>void do
	begin info(q)←m-info(q); q←link(q);
	end

@ Reversing the order of a linked list is best thought of as the process of
popping nodes off one stack and pushing them on another. In this case we
pop from stack~|q| and push to stack~|r|.

@<Reflect the edge-and-weight data in |sorted(p)|@>=
q←sorted(p); r←sentinel;
while q≠sentinel do
	begin s←link(q); link(q)←r; r←q; info(r)←m-info(q); q←s;
	end;
sorted(p)←r

@ The |unsorted| edges of a row are merged into the |sorted| ones by
a subroutine called |sort_edges|. It uses simple insertion sort,
followed by a merge, because the unsorted list is supposedly quite short.
However, the unsorted list is assumed to be nonempty.

@p procedure sort_edges(@!h:pointer); {|h| is a row header}
label done;
var @!k:halfword; {key register that we compare to |info(q)|}
@!p,@!q,@!r,@!s:pointer;
begin r←unsorted(h); unsorted(h)←null;
p←link(r); link(r)←sentinel; link(temp_head)←r;
while p>void do {sort node |p| into the list that starts at |temp_head|}
	begin k←info(p); q←temp_head;
	repeat r←q; q←link(r);
	until k≤info(q);
	link(r)←p; r←link(p); link(p)←q; p←r;
	end;
@<Merge the |temp_head| list into |sorted(h)|@>;
end;

@ In this step we use the fact that |@!sorted(h)=link(sorted_loc(h))|.

@<Merge the |temp_head| list into |sorted(h)|@>=
begin r←sorted_loc(h); q←link(r); p←link(temp_head);
loop@+	begin k←info(p);
	while k>info(q) do
		begin r←q; q←link(r);
		end;
	link(r)←p; s←link(p); link(p)←q;
	if s=sentinel then goto done;
	r←p; p←s;
	end;
done:end

@ The |cull_edges| procedure ``optimizes'' an edge structure by making
all the pixel weights either 0 or~1. The weight will be~1 after the operation
if and only if it was |≥w_plus| or |≤w_minus| before, where |w_plus| is
positive and |w_minus| is negative. (In particular, zero-weight pixels
will remain of weight zero. This is fortunate, because there are infinitely
many of them.)

The procedure also computes the tightest possible bounds on the resulting
data, by updating |m_min|, |m_max|, |n_min|, and~|n_max|.

@p procedure cull_edges(@!w_plus,@!w_minus:integer);
label done;
var @!p,@!q,@!r,@!s:pointer; {for list manipulation}
@!w:integer; {new weight after culling}
@!d:integer; {data register for unpacking}
@!m:integer; {the previous column number, including |m_offset|}
@!mm:integer; {the next column number, including |m_offset|}
@!ww:integer; {accumulated weight before culling}
@!prev_w:integer; {value of |w| before column |m|}
@!n,@!min_n,@!max_n:pointer; {current and extreme row numbers}
@!min_d,@!max_d:pointer; {extremes of the new edge-and-weight data}
begin min_d←max_halfword; max_d←min_halfword;
min_n←max_halfword; max_n←min_halfword;@/
p←link(cur_edges); n←n_min(cur_edges);
while p≠cur_edges do
	begin if unsorted(p)>void then sort_edges(p);
	if sorted(p)>sentinel then
		@<Cull superfluous edge-weight entries from |sorted(p)|@>;
	p←link(p); incr(n);
	end;
@<Delete empty rows at the top and/or bottom;
	update the boundary values in the header@>;
last_window_time(cur_edges)←0;
end;

@ The entire |sorted| list is returned to available memory in this step;
a new list is built starting (temporarily) at |temp_head|.
Since several edges can occur at the same column, we need to be looking
ahead of where the actual culling takes place. This means that it's
slightly tricky to get the iteration started and stopped.

@<Cull superfluous...@>=
begin r←temp_head; q←sorted(p); ww←0; m←1000000; prev_w←0;
loop@+	begin if q=sentinel then mm←1000000
	else	begin d←ho(info(q)); mm←d div 8; ww←ww+(d mod 8)-zero_w;
		end;
	if mm>m then
		begin @<Insert an edge-weight for edge |m|, if the new pixel
			weight has changed@>;
		if q=sentinel then goto done;
		end;
	m←mm;
	if (ww≥w_plus)∨(ww≤w_minus) then w←1@+else w←0;
	s←link(q); free_avail(q); q←s;
	end;
done: link(r)←sentinel; sorted(p)←link(temp_head);
if r≠temp_head then @<Update the max/min amounts@>;
end

@ @<Insert an edge-weight for edge |m|, if...@>=
if w≠prev_w then
	begin s←get_avail; link(r)←s;
	info(s)←8*m+min_halfword+zero_w+w-prev_w;
	r←s; prev_w←w;
	end

@ @<Update the max/min amounts@>=
begin if min_n=max_halfword then min_n←n;
max_n←n;
if min_d>info(link(temp_head)) then min_d←info(link(temp_head));
if max_d<info(r) then max_d←info(r);
end

@ @<Delete empty rows at the top and/or bottom...@>=
if min_n>max_n then @<Delete all the row headers@>
else	begin n←n_min(cur_edges); n_min(cur_edges)←min_n;
	while min_n>n do
		begin p←link(cur_edges); link(cur_edges)←link(p);
		knil(link(p))←cur_edges;
		free_node(p,row_node_size); incr(n);
		end;
	n←n_max(cur_edges); n_max(cur_edges)←max_n;
	n_pos(cur_edges)←max_n+1; n_rover(cur_edges)←cur_edges;
	while max_n<n do
		begin p←knil(cur_edges); knil(cur_edges)←knil(p);
		link(knil(p))←cur_edges;
		free_node(p,row_node_size); decr(n);
		end;
	m_min(cur_edges)←((ho(min_d)) div 8)-m_offset(cur_edges)+zero_field;
	m_max(cur_edges)←((ho(max_d)) div 8)-m_offset(cur_edges)+zero_field;
	end

@ We get here if the edges have been entirely culled away.

@<Delete all the row headers@>=
begin p←link(cur_edges);
while p≠cur_edges do
	begin q←link(p); free_node(p,row_node_size); p←q;
	end;
init_edges(cur_edges);
end


@ The last and most difficult routine for transforming an edge structure---and
the most interesting one!---is |xy_swap_edges|, which interchanges the
r\↑↑Doles of rows and columns. Its task can be viewed as the job of
creating an edge structure that contains only horizontal edges, linked
together in columns, given an edge structure that contains only
vertical edges linked together in rows; we must do this without changing
the implied pixel weights.

Given any two adjacent rows of an edge structure, it is not difficult to
determine the horizontal edges that lie ``between'' them: We simply look
for vertically adjacent pixels that have different weight, and insert
a horizontal edge containing the difference in weights. Every horizontal
edge determined in this way should be put into an appropriate linked
lists. Since random access to these linked lists is desirable, we use
the |move| array to hold the list heads. If we work through the given
edge structure from top to bottom, the constructed lists will not need
to be sorted, since they will already be in order.

The following algorithm makes use of some ideas suggested by John Hobby.
@↑Hobby, John Douglas@>
It assumes that the edge structure is non-null, i.e., that |link(cur_edges)
≠cur_edges| and |m_max(cur_edges)≥m_min(cur_edges)|.

@p procedure xy_swap_edges; {interchange |x| and |y| in |cur_edges|}
label done;
var @!m_magic,@!n_magic:integer; {special values that account for offsets}
@!p,@!q,@!r,@!s:pointer; {pointers that traverse the given structure}
@<Other local variables for |xy_swap_edges|@>@;
begin @<Initialize the array of new edge list heads@>;
@<Insert blank rows at the top and bottom, and set |p| to the new top row@>;
@<Compute the magic offset values@>;
repeat q←knil(p);@+if unsorted(q)>void then sort_edges(q);
@<Insert the horizontal edges defined by adjacent rows |p,q|,
	and destroy row~|p|@>;
p←q; n_magic←n_magic-8;
until knil(p)=cur_edges;
free_node(p,row_node_size); {now all original rows have been recycled}
@<Adjust the header to reflect the new edges@>;
end;

@ Here we don't bother to keep the |link| entries up to date, since the
procedure looks only at the |knil| fields as it destroys the former
edge structure.

@<Insert blank rows at the top and bottom...@>=
p←get_node(row_node_size); sorted(p)←sentinel; unsorted(p)←null;@/
knil(p)←cur_edges; knil(link(cur_edges))←p; {the new bottom row}
p←get_node(row_node_size); sorted(p)←sentinel;
knil(p)←knil(cur_edges); {the new top row}

@ The new lists will become |sorted| lists later, so we initialize
empty lists to |sentinel|.

@<Initialize the array of new edge list heads@>=
m_spread←m_max(cur_edges)-m_min(cur_edges); {this is |≥0| by assumption}
if m_spread>move_size then overflow("move table size",move_size);
@:METAFONT capacity exceeded move table size}{\quad move table size@>
for j←0 to m_spread do move[j]←sentinel

@ @<Other local variables for |xy_swap_edges|@>=
@!m_spread:integer; {the difference between |m_max| and |m_min|}
@!j,@!jj:0..move_size; {indices into |move|}
@!m,@!mm:integer; {|m| values at vertical edges}
@!pd,@!rd:integer; {data fields from edge-and-weight nodes}
@!pm,@!rm:integer; {|m| values from edge-and-weight nodes}
@!w:integer; {the difference in accumulated weight}
@!ww:integer; {as much of |w| that can be stored in a single node}
@!dw:integer; {an increment to be added to |w|}

@ At the point where we test |w≠0|, variable |w| contains
the accumulated weight from edges already passed in
row~|p| minus the accumulated weight from edges already passed in row~|q|.

@<Insert the horizontal edges defined by adjacent rows |p,q|...@>=
r←sorted(p); free_node(p,row_node_size); p←r;@/
pd←ho(info(p)); pm←pd div 8;@/
r←sorted(q); rd←ho(info(r)); rm←rd div 8; w←0;
loop@+	begin if pm<rm then mm←pm@+else mm←rm;
	if w≠0 then
		@<Insert horizontal edges of weight |w| between |m| and~|mm|@>;
	if pd<rd then
		begin dw←(pd mod 8)-zero_w;
		@<Advance pointer |p| to the next vertical edge,
			after destroying the previous one@>;
		end
	else	begin if r=sentinel then goto done; {|rd=pd=ho(max_halfword)|}
		dw←-((rd mod 8)-zero_w);
		@<Advance pointer |r| to the next vertical edge@>;
		end;
	m←mm; w←w+dw;
	end;
done:

@ @<Advance pointer |r| to the next vertical edge@>=
r←link(r); rd←ho(info(r)); rm←rd div 8

@ @<Advance pointer |p| to the next vertical edge...@>=
s←link(p); free_avail(p); p←s; pd←ho(info(p)); pm←pd div 8

@ Certain ``magic'' values are needed to make the following code work,
due to the various offsets in our data structure. For now, let's not
worry about their precise values; we shall compute |m_magic| and |n_magic|
later, after we see what the code looks like.

@ @<Insert horizontal edges of weight |w| between |m| and~|mm|@>=
if m≠mm then
	begin if mm-m_magic≥move_size then confusion("xy");
@:this can't happen xy}{\quad xy@>
	extras←(abs(w)-1) div 3;
	if extras>0 then
		begin if w>0 then xw←+3@+else xw←-3;
		ww←w-extras*xw;
		end
	else ww←w;
	repeat j←m-m_magic;
	for k←1 to extras do
		begin s←get_avail; info(s)←n_magic+xw;
		link(s)←move[j]; move[j]←s;
		end;
	s←get_avail; info(s)←n_magic+ww;
	link(s)←move[j]; move[j]←s;@/
	incr(m);
	until m=mm;
	end

@ @<Other local variables for |xy...@>=
@!extras:integer; {the number of additional nodes to make weights |>3|}
@!xw:-3..3; {the additional weight in extra nodes}
@!k:integer; {loop counter for inserting extra nodes}

@ At the beginning of this step, |move[m_spread]=sentinel|, because no
horizontal edges will extend to the right of column |m_max(cur_edges)|.

@<Adjust the header to reflect the new edges@>=
move[m_spread]←0; j←0;
while move[j]=sentinel do incr(j);
if j=m_spread then init_edges(cur_edges)
else	begin mm←m_min(cur_edges);
	m_min(cur_edges)←n_min(cur_edges);
	m_max(cur_edges)←n_max(cur_edges)+1;
	m_offset(cur_edges)←zero_field;
	jj←m_spread-1;
	while move[jj]=sentinel do decr(jj);
	n_min(cur_edges)←j+mm; n_max(cur_edges)←jj+mm; q←cur_edges;
	repeat p←get_node(row_node_size); link(q)←p; knil(p)←q;
	sorted(p)←move[j]; unsorted(p)←null; incr(j); q←p;
	until j>jj;
	link(q)←cur_edges; knil(cur_edges)←q;
	n_pos(cur_edges)←n_max(cur_edges)+1; n_rover(cur_edges)←cur_edges;
	last_window_time(cur_edges)←0;
	end;

@ The values of |m_magic| and |n_magic| can be worked out by trying the
code above on a small example; if they work correctly in simple cases,
they should work in general.

@<Compute the magic offset values@>=
m_magic←m_min(cur_edges)+m_offset(cur_edges)-zero_field;
n_magic←8*n_max(cur_edges)+8+zero_w-min_halfword

@ Now let's look at the subroutine that merges the edges from a given
edge structure into |cur_edges|. The given edge structure loses all its
edges.

@p procedure merge_edges(@!h:pointer);
label done;
var @!p,@!q,@!r,@!pp,@!qq,@!rr:pointer; {list manipulation registers}
@!n:integer; {row number}
@!k:halfword; {key register that we compare to |info(q)|}
@!delta:integer; {change to the edge/weight data}
begin if link(h)≠h then
	begin if (m_min(h)<m_min(cur_edges))∨(m_max(h)>m_max(cur_edges))∨@|
		(n_min(h)<n_min(cur_edges))∨(n_max(h)>n_max(cur_edges)) then
		edge_prep(m_min(h)-zero_field,m_max(h)-zero_field,
			n_min(h)-zero_field,n_max(h)-zero_field+1);
	if m_offset(h)≠m_offset(cur_edges) then
		@<Adjust the data of |h| to account for a difference of offsets@>;
	n←n_min(cur_edges); p←link(cur_edges); pp←link(h);
	while n<n_min(h) do
		begin incr(n); p←link(p);
		end;
	repeat @<Merge row |pp| into row |p|@>;
	pp←link(pp); p←link(p);
	until pp=h;
	end;
end;

@ @<Adjust the data of |h| to account for a difference of offsets@>=
begin pp←link(h); delta←8*(m_offset(cur_edges)-m_offset(h));
repeat qq←sorted(pp);
while qq>sentinel do
	begin info(qq)←info(qq)+delta; qq←link(qq);
	end;
qq←unsorted(pp);
while qq>void do
	begin info(qq)←info(qq)+delta; qq←link(qq);
	end;
pp←link(pp);
until pp=h;
end

@ The |sorted| and |unsorted| lists are merged separately. After this
step, row~|pp| will have no edges remaining, since they will all have
been merged into row~|p|.

@<Merge row |pp|...@>=
qq←unsorted(pp);
if qq>void then
	if unsorted(p)≤void then unsorted(p)←qq
	else	begin while link(qq)>void do qq←link(qq);
		link(qq)←unsorted(p); unsorted(p)←unsorted(pp);
		end;
unsorted(pp)←null; qq←sorted(pp);
if qq≠sentinel then
	begin if unsorted(p)=void then unsorted(p)←null;
	sorted(pp)←sentinel; r←sorted_loc(p); q←link(r); {|q=sorted(p)|}
	if q=sentinel then sorted(p)←qq
	else loop@+begin k←info(qq);
		while k>info(q) do
			begin r←q; q←link(r);
			end;
		link(r)←qq; rr←link(qq); link(qq)←q;
		if rr=sentinel then goto done;
		r←qq; qq←rr;
		end;
	end;
done:

@ \MF\ will display new edges as they are being computed, if |tracing_edges|
is positive. In order to keep such data reasonably compact, only the
points at which the path makes a $90↑\circ$ or $180↑\circ$ turn are listed.

The tracing algorithm must remember some past history in order to suppress
unnecessary data. Three variables |trace_x|, |trace_y|, and |trace_yy|
provide this history: The last coordinates printed were |(trace_x,trace_y)|,
and the previous edge traced ended at |(trace_x,trace_yy)|. Before anything
at all has been traced, |trace_x=-4096|.

@<Glob...@>=
@!trace_x:integer; {$x$-coordinate most recently shown in a trace}
@!trace_y:integer; {$y$-coordinate most recently shown in a trace}
@!trace_yy:integer; {$y$-coordinate most recently encountered}

@ Edge tracing is initiated by the |begin_edge_tracing| routine,
continued by the |trace_a_corner| routine, and terminated by the
|end_edge_tracing| routine.

@p procedure begin_edge_tracing;
begin print_diagnostic("Tracing edges","");
print(" (weight "); print_int(cur_wt); print_char(")"); trace_x←-4096;
end;
@#
procedure trace_a_corner;
begin if file_offset>max_print_line-13 then print_nl("");
print_char("("); print_int(trace_x); print_char(","); print_int(trace_yy);
print_char(")"); trace_y←trace_yy;
end;
@#
procedure end_edge_tracing;
begin if trace_x=-4096 then print_nl("(No new edges added.)")
@.No new edges added@>
else	begin trace_a_corner; print_char(".");
	end;
end_diagnostic(true);
end;

@ Just after a new edge weight has been put into the |info| field of
node~|r|, in row~|n|, the following routine continues an ongoing trace.

@p procedure trace_new_edge(@!r:pointer;@!n:integer);
var @!d:integer; {temporary data register}
@!w:-3..3; {weight associated with an edge transition}
@!m,@!n0,@!n1:integer; {column and row numbers}
begin d←ho(info(r)); w←(d mod 8)-zero_w; m←(d div 8)-m_offset(cur_edges);
if w=cur_wt then
	begin n0←n+1; n1←n;
	end
else	begin n0←n; n1←n+1;
	end; {the edges runs from |(m,n0)| to |(m,n1)|}
if m≠trace_x then
	begin if trace_x=-4096 then
		begin print_nl(""); trace_yy←n0;
		end
	else if trace_yy≠n0 then print_char("?") {shouldn't happen}
	else trace_a_corner;
	trace_x←m; trace_a_corner;
	end
else	begin if n0≠trace_yy then print_char("!"); {shouldn't happen}
	if ((n0<n1)∧(trace_y>trace_yy))∨((n0>n1)∧(trace_y<trace_yy)) then
		trace_a_corner;
	end;
trace_yy←n1;
end;

@ One way to put new edge weights into an edge structure is to use the
following routine, which simply draws a straight line from |(x0,y0)| to
|(x1,y1)|. More precisely, it introduces weights for the edges of the
discrete path $\bigl(\lfloor t[x_0,x_1]+{1\over2}+\epsilon\rfloor,
\lfloor t[y_0,y_1]+{1\over2}+\epsilon↑2\rfloor\bigr)$,
as $t$ varies from 0 to~1, where $\epsilon$ is an extremely small
positive number.

The structure header is assumed to be |cur_edges|; downward edge weights
will be |cur_wt|, while upward ones will be |-cur_wt|.

Of course, this subroutine will be called only in connection with others
that eventually draw a complete cycle, so that the sum of the edge weights
in each row will be zero whenever the row is displayed.

@p procedure line_edges(@!x0,@!y0,@!x1,@!y1:scaled);
label done,done1;
var @!m0,@!n0,@!m1,@!n1:integer; {rounded and unscaled coordinates}
@!delx,@!dely:scaled; {the coordinate differences of the line}
@!yt:scaled; {smallest |y| coordinate that rounds the same as |y0|}
@!tx:scaled; {tentative change in |x|}
@!p,@!r:pointer; {list manipulation registers}
@!base:integer; {amount added to edge-and-weight data}
@!n:integer; {current row number}
begin n0←round_unscaled(y0);
n1←round_unscaled(y1);
if n0≠n1 then
	begin m0←round_unscaled(x0); m1←round_unscaled(x1);
	delx←x1-x0; dely←y1-y0;
	yt←n0*unity-half_unit; y0←y0-yt; y1←y1-yt;
	if n0<n1 then @<Insert upward edges for a line@>
	else @<Insert downward edges for a line@>;
	n_rover(cur_edges)←p; n_pos(cur_edges)←n+zero_field;
	end;
end;

@ Here we are careful to cancel any effect of rounding error.

@<Insert upward edges for a line@>=
begin base←8*m_offset(cur_edges)+min_halfword+zero_w-cur_wt;
if m0≤m1 then edge_prep(m0,m1,n0,n1)@+else edge_prep(m1,m0,n0,n1);
@<Move to row |n0|, pointed to by |p|@>;
y0←unity-y0;
loop@+	begin r←get_avail; link(r)←unsorted(p); unsorted(p)←r;@/
	tx←take_fraction(delx,make_fraction(y0,dely));
	if ab_vs_cd(delx,y0,dely,tx)<0 then decr(tx);
		{now $|tx|=\lfloor|y0|\cdot|delx|/|dely|\rfloor$}
	info(r)←8*round_unscaled(x0+tx)+base;@/
	y1←y1-unity;
	if internal[tracing_edges]>0 then trace_new_edge(r,n);
	if y1<unity then goto done;
	p←link(p); y0←y0+unity; incr(n);
	end;
done: end

@ @<Insert downward edges for a line@>=
begin base←8*m_offset(cur_edges)+min_halfword+zero_w+cur_wt;
if m0≤m1 then edge_prep(m0,m1,n1,n0)@+else edge_prep(m1,m0,n1,n0);
decr(n0); @<Move to row |n0|, pointed to by |p|@>;
loop@+	begin r←get_avail; link(r)←unsorted(p); unsorted(p)←r;@/
	tx←take_fraction(delx,make_fraction(y0,dely));
	if ab_vs_cd(delx,y0,dely,tx)<0 then incr(tx);
		{now $|tx|=\lceil|y0|\cdot|delx|/|dely|\rceil$, since |dely<0|}
	info(r)←8*round_unscaled(x0-tx)+base;@/
	y1←y1+unity;
	if internal[tracing_edges]>0 then trace_new_edge(r,n);
	if y1≥0 then goto done1;
	p←knil(p); y0←y0+unity; decr(n);
	end;
done1: end

@ @<Move to row |n0|, pointed to by |p|@>=
n←n_pos(cur_edges)-zero_field; p←n_rover(cur_edges);
if n≠n0 then
	if n<n0 then
		repeat incr(n); p←link(p);
		until n=n0
	else	repeat decr(n); p←knil(p);
		until n=n0

@ \MF\ inserts most of its edges into edge structures via the
|move_to_edges| subroutine, which uses the data stored in the |move| array
to specify a sequence of ``rook moves.'' The starting point |(m0,n0)|
and finishing point |(m1,n1)| of these moves, as seen from the standpoint
of the first octant, are supplied as parameters; the moves should, however,
be rotated into a given octant, supplied as a further parameter.
(We're going to study octant transformations in great detail later; the
reader may wish to come back to this part of the program after mastering
the mysteries of octants.)

The rook moves themselves are defined as follows, from a |first_octant|
point of view: ``Go right |move[k]| steps, then go up one, for |0≤k<n1-n0|;
then go right |move[n1-n0]| steps and stop.'' The sum of |move[k]|
for |0≤k≤n1-n0| will be equal to |m1-m0|.

As in the |line_edges| routine, we use |+cur_wt| as the weight of
all downward edges and |-cur_wt| as the weight of all upward edges,
after the moves have been rotated to the proper octant direction.

There are two main cases to consider: \\{fast\_case} is for moves that
travel in the direction of octants 1, 4, 5, and~8, while \\{slow\_case}
is for moves that travel toward octants 2, 3, 6, and~7. The latter directions
are comparatively cumbersome because they generate more upward or downward
edges; a curve that travels horizontally doesn't produce any edges at all,
but a curve that travels vertically touches lots of rows.

@d fast_case_up=60 {for octants 1 and 4}
@d fast_case_down=61 {for octants 5 and 8}
@d slow_case_up=62 {for octants 2 and 3}
@d slow_case_down=63 {for octants 6 and 7}

@p procedure move_to_edges(@!m0,@!n0,@!m1,@!n1:integer;@!octant:small_number);
label fast_case_up,fast_case_down,slow_case_up,slow_case_down,done;
var @!delta:0..move_size; {extent of |move| data}
@!k:0..move_size; {index into |move|}
@!p,@!r:pointer; {list manipulation registers}
@!dx:integer; {change in edge-weight |info| when |x| changes by 1}
@!edge_and_weight:integer; {|info| to insert}
@!j:integer; {number of consecutive vertical moves}
@!n:integer; {the current row pointed to by |p|}
debug @!sum:integer;@+gubed@;@/
begin delta←n1-n0;
debug sum←move[0]; for k←1 to delta do sum←sum+abs(move[k]);
if sum≠m1-m0 then confusion("0");@+gubed@;@/
@<Prepare for and switch to the appropriate case, based on |octant|@>;
fast_case_up:@<Add edges for first or fourth octants, then |goto done|@>;
fast_case_down:@<Add edges for fifth or eighth octants, then |goto done|@>;
slow_case_up:@<Add edges for second or third octants, then |goto done|@>;
slow_case_down:@<Add edges for sixth or seventh octants, then |goto done|@>;
done: n_pos(cur_edges)←n+zero_field; n_rover(cur_edges)←p;
end;

@ @<Prepare for and switch to the appropriate case, based on |octant|@>=
case octant of
first_octant:begin dx←8; edge_prep(m0,m1,n0,n1); goto fast_case_up;
	end;
second_octant:begin dx←8; edge_prep(n0,n1,m0,m1); goto slow_case_up;
	end;
third_octant:begin dx←-8; edge_prep(-n1,-n0,m0,m1); negate(n0);
	goto slow_case_up;
	end;
fourth_octant:begin dx←-8; edge_prep(-m1,-m0,n0,n1); negate(m0);
	goto fast_case_up;
	end;
fifth_octant:begin dx←-8; edge_prep(-m1,-m0,-n1,-n0); negate(m0);
	goto fast_case_down;
	end;
sixth_octant:begin dx←-8; edge_prep(-n1,-n0,-m1,-m0); negate(n0);
	goto slow_case_down;
	end;
seventh_octant:begin dx←8; edge_prep(n0,n1,-m1,-m0); goto slow_case_down;
	end;
eighth_octant:begin dx←8; edge_prep(m0,m1,-n1,-n0); goto fast_case_down;
	end;
end; {there are only eight octants}

@ @<Add edges for first or fourth octants, then |goto done|@>=
@<Move to row |n0|, pointed to by |p|@>;
if delta>0 then
	begin k←0;
	edge_and_weight←8*(m0+m_offset(cur_edges))+min_halfword+zero_w-cur_wt;
	repeat edge_and_weight←edge_and_weight+dx*move[k];
	fast_get_avail(r); link(r)←unsorted(p); info(r)←edge_and_weight;
	if internal[tracing_edges]>0 then trace_new_edge(r,n);
	unsorted(p)←r; p←link(p); incr(k); incr(n);
	until k=delta;
	end;
goto done

@ @<Add edges for fifth or eighth octants, then |goto done|@>=
n0←-n0-1; @<Move to row |n0|, pointed to by |p|@>;
if delta>0 then
	begin k←0;
	edge_and_weight←8*(m0+m_offset(cur_edges))+min_halfword+zero_w+cur_wt;
	repeat edge_and_weight←edge_and_weight+dx*move[k];
	fast_get_avail(r); link(r)←unsorted(p); info(r)←edge_and_weight;
	if internal[tracing_edges]>0 then trace_new_edge(r,n);
	unsorted(p)←r; p←knil(p); incr(k); decr(n);
	until k=delta;
	end;
goto done

@ @<Add edges for second or third octants, then |goto done|@>=
edge_and_weight←8*(n0+m_offset(cur_edges))+min_halfword+zero_w-cur_wt;
n0←m0; k←0; @<Move to row |n0|, pointed to by |p|@>;
repeat j←move[k];
while j>0 do
	begin fast_get_avail(r); link(r)←unsorted(p); info(r)←edge_and_weight;
	if internal[tracing_edges]>0 then trace_new_edge(r,n);
	unsorted(p)←r; p←link(p); decr(j); incr(n);
	end;
edge_and_weight←edge_and_weight+dx; incr(k);
until k>delta;
goto done

@ @<Add edges for sixth or seventh octants, then |goto done|@>=
edge_and_weight←8*(n0+m_offset(cur_edges))+min_halfword+zero_w+cur_wt;
n0←-m0-1; k←0; @<Move to row |n0|, pointed to by |p|@>;
repeat j←move[k];
while j>0 do
	begin fast_get_avail(r); link(r)←unsorted(p); info(r)←edge_and_weight;
	if internal[tracing_edges]>0 then trace_new_edge(r,n);
	unsorted(p)←r; p←knil(p); decr(j); decr(n);
	end;
edge_and_weight←edge_and_weight+dx; incr(k);
until k>delta;
goto done

@ All the hard work of building an edge structure is undone by the following
subroutine.

@<Declare the recycling subroutines@>=
procedure toss_edges(@!h:pointer);
var @!p,@!q:pointer; {for list manipulation}
begin q←link(h);
while q≠h do
	begin flush_list(sorted(q));
	if unsorted(q)>void then flush_list(unsorted(q));
	p←q; q←link(q); free_node(p,row_node_size);
	end;
free_node(h,edge_header_size);
end;